package entryNodeOfLoop;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

public class Solution {
    public Optional<ListNode> entryNodeOfLoop(ListNode head){
        ListNode next = head ;
        List<ListNode> bitset = new ArrayList<>();
        do{
            if(bitset.indexOf(next) == -1){
                bitset.add(next);
            }else {
                return Optional.of(next);
            }

        }while ((next = next.getNext()) != null);
        return Optional.ofNullable(null);
    }
    public Optional<ListNode> entryNodeOfLoop2(ListNode head){
        ListNode fast = head ;
        ListNode slow = head ;
        ListNode next = head ;
        do{
            if(fast != null){
                fast = fast.getNext();
            }

            if(fast != null){
                fast = fast.getNext();
            }

            if(slow != null){
                slow = slow.getNext();
            }
        }while( fast != null && !fast.equals(slow) );

        // fast 和 slow 相等了，说有环的存在
        if( fast.equals(slow)){
            fast = head ;
            while(fast != null && slow != null && !fast.equals(slow)){
                fast = fast.getNext();
                slow = slow.getNext();
            }
        }
        return Optional.ofNullable(fast);

    }
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.setNext(l2);
        l2.setNext(l3);
        l3.setNext(l4);
        l4.setNext(l5);
        l5.setNext(l4);
        Solution s = new Solution();
        Optional<ListNode> listNode = s.entryNodeOfLoop2(l1);
        listNode.ifPresent( x -> System.out.println(x.getVar()));
    }
}
